package Preferred_algorithm.Topic7_Divide_and_conquer_algorithm;

public class Inversion_Count {
    int[] tmp, nums;

    public int reversePairs(int[] _nums) {
        nums = _nums;
        int n = nums.length;
        tmp = new int[n];
        return mergeSort(0, n - 1);
    }

    // mergeSort 的任务是找出传入区间有多少个逆序对，并且顺手排序
    public int mergeSort(int left, int right) {

        // 只有一个元素，或者没有元素，这种情况不可能有逆序对
        if (left >= right) {
            return 0;
        }

        int ret = 0;
        // 1. 选择一个中间点，把数组划分成两个部分
        int mid = (left + right) / 2;
        // [left , mid] [mid+1 , right]

        // 2. 左半部分的个数 + 排序 +右边部分的个数 + 排序
        ret += mergeSort(left, mid);
        ret += mergeSort(mid + 1, right);

        // 3. 一左一右逆序对的个数
        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right) {
            // 升序
            if (nums[cur1] <= nums[cur2]) {
                tmp[i++] = nums[cur1++];
            } else {
                ret += mid - cur1 + 1;
                tmp[i++] = nums[cur2++];
            }
        }

        // 4. 处理没有移动完的指针
        while (cur1 <= mid) tmp[i++] = nums[cur1++];
        while (cur2 <= right) tmp[i++] = nums[cur2++];

        // 5. 还原
        for (int j = left; j <= right; j++)
            nums[j] = tmp[j - left];

        return ret;
    }

    public int mergeSort1(int left, int right) {

        // 只有一个元素，或者没有元素，这种情况不可能有逆序对
        if (left >= right) {
            return 0;
        }

        int ret = 0;
        // 1. 选择一个中间点，把数组划分成两个部分
        int mid = (left + right) / 2;
        // [left , mid] [mid+1 , right]

        // 2. 左半部分的个数 + 排序 +右边部分的个数 + 排序
        ret += mergeSort(left, mid);
        ret += mergeSort(mid + 1, right);

        // 3. 一左一右逆序对的个数
        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right) {
            // 降序
            if (nums[cur1] <= nums[cur2]) {
                tmp[i++] = nums[cur2++];
            } else {
                ret += right - cur2 + 1;
                tmp[i++] = nums[cur1++];
            }
        }

        // 4. 处理没有移动完的指针
        while (cur1 <= mid) tmp[i++] = nums[cur1++];
        while (cur2 <= right) tmp[i++] = nums[cur2++];

        // 5. 还原
        for (int j = left; j <= right; j++)
            nums[j] = tmp[j - left];

        return ret;
    }
}
